|
In graph theory, Hedetniemi's conjecture, named after Stephen T. Hedetniemi, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that :χ(''G'' × ''H'') = min . Here χ(''G'') denotes the chromatic number of an undirected finite graph ''G''. An inequality in one direction is easy: if ''G'' is ''k''-colored, one can ''k''-color ''G'' × ''H'' by using the same coloring for each copy of ''G'' in the product, so χ(''G'' × ''H'') ≤ χ(''G''). For the same reason χ(''G'' × ''H'') ≤ χ(''H''); therefore, χ(''G'' × ''H'') ≤ min . Thus, Hedetniemi's conjecture amounts to the assertion that tensor products can't be colored with an unexpectedly small number of colors. Hedetniemi formulated his conjecture in 1966 based on the inequality described above. Hedetniemi's conjecture has also been called the Lovász-Hedetniemi conjecture . It cannot be generalized to infinite graphs: gave an example of two infinite graphs, each requiring an uncountable number of colors, such that their product can be colored with only countably many colors. proved that in the constructible universe, for every infinite cardinal , there exist a pair of graphs of chromatic number greater than , such that their product can still be colored with only countably many colors. == Example == Suppose that ''G'' and ''H'' are both cycle graphs ''Cm'' and ''Cn''. Then the edges of ''G'' × ''H'' can be grouped into cycles with length equal to the least common multiple of ''m'' and ''n''. Thus, if both ''G'' and ''H'' have an odd number of vertices and therefore require three colors, the product ''G'' × ''H'' will contain odd cycles and will also require three colors. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hedetniemi's conjecture」の詳細全文を読む スポンサード リンク
|